package com.leetcode.tree.traversal;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/8/1 18:20
 */
public class PostBuildTree_106 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        if (len == 0) return null;
        return buildTree(postorder, 0, len - 1, inorder, 0, len - 1);
    }

    private TreeNode buildTree(int[] p, int pl, int pr, int[] in, int il, int ir) {
        if (pl > pr) return null;
        int k = il;
        while (p[pr] != in[k]) k++;
        int right = ir - k;
        TreeNode root = new TreeNode(p[pr]);
        root.left = buildTree(p, pl, pr - right - 1, in, il, k - 1);
        root.right = buildTree(p, pr - right, pr - 1, in, k + 1, ir);
        return root;
    }

    static class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            return buildTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
        }

        private TreeNode buildTree(int[] post, int pl, int pr, int[] in, int il, int ir) {
            if (pr < pl) return null;
            int k;
            for (k = il; k != post[pr]; k++) ;
            int right = ir - k;
            TreeNode node = new TreeNode(in[k]);
            node.left = buildTree(post, pl, pr - right - 1, in, il, k - 1);
            node.right = buildTree(post, pr - right, pr - 1, in, k + 1, ir);
            return node;
        }

    }

}
